package com.zy.algorithm.sort;

import java.util.List;

/**
 * @author ZhaoYi
 * @date 2023/12/14 14:33
 * <p>
 * 选择排序（Selection Sort）：
 * <p>
 * 思想：每次选择剩余未排序部分的最小（或最大）元素，放到已排序部分的末尾。
 * 特点：时间复杂度为O(n^2)，稳定性较差(相等的相对位置可能变化)。
 */
public class SelectionSort<T extends Comparable<? super T>> implements ISort<T> {
    @Override
    public List<T> sort(List<T> list) {
        if (list == null || list.size() <= 1) {
            return list;
        }

        //已经有序的部分数量
        int finish = 0;
        while (finish < list.size()) {
            //找最小
            T minTmp = list.get(finish);
            int minIndex = -1;
            for (int i = finish + 1; i < list.size(); i++) {
                if (list.get(i).compareTo(minTmp) < 0) {
                    minTmp = list.get(i);
                    minIndex = i;
                }
            }

            if (minIndex > 0) {
                swap(list, finish, minIndex);
            }
            finish++;
        }
        return list;
    }

    private void swap(List<T> list, int i, int minIndex) {
        T tmp = list.get(i);
        list.set(i, list.get(minIndex));
        list.set(minIndex, tmp);
    }
}
